#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2022/4/28 14:15
# @Software: PyCharm
# @File    : l42_trap.py


class Solution:
    def __init__(self):
        '''
        核心原理：
        1先正序遍历数组，将数据分成n个区间，区间满足条件如下：
        起点：他的左边是等差数列，（此时不会接住水）
        终点：右边第一个大于等于起点的点
        2此时可能还有有剩余数（最后一个区间的终点的右边所有数都小于该值），则倒序遍历剩余的数组，同样的思路寻找区间，保证最后一个区间的终点就是正序遍历的最后一个区间的终点
        3.计算这些区间的可接雨水量：区间中的每个数于min(终点,起点)的差的总和
        '''
        pass

    def trap_1(self, height: list[int]) -> int:
        self.ranges, self.is_end, self.left = [], False, 0

        def calc(ranges):
            rule = min(height[ranges[0]], height[ranges[1]])
            res = 0
            start, end, dir = ranges
            if dir > 0:
                start = start + 1
            for i in range(start, end, dir):
                res += max(rule - height[i], 0)
            return res

        def find_range(start, end, dir):
            has_left, tmp = False, []
            self.left = start
            for i in range(start, end, dir):
                if not has_left:
                    if height[i] >= height[self.left]:
                        self.left = i
                    else:
                        tmp.append(self.left)
                        has_left = True

                else:
                    if height[i] >= height[self.left]:
                        tmp.append(i)
                        tmp.append(dir)
                        last = i
                        self.is_end = last == end
                        self.ranges.append(tmp)
                        tmp = []
                        has_left = False
                        self.left = i

        start, end, dir = self.left, len(height), 1
        # 先找左区间
        find_range(start, end, dir)
        left_end = self.left  # 左区间的终点
        # 再找右区间
        has_left = len(self.ranges) > 0
        if not self.is_end:  # 还有剩余，再找右区间
            find_range(end - 1, self.left - 1, -1)
            if has_left:
                self.ranges[-1][1] = left_end  # 最后一个区间，取最左值
        res = 0
        for r in self.ranges:
            res += calc(r)
        return res

    def trap(self, height: list[int]) -> int:
        '''
        双指针
        一个位置能接多少水取决于左右两边的最大值left_max,right_max中的较小者
        所以:分别从左右两边往中间寻找
        1从左往右找时，此时的左边最大值是可信的，如果此时的left_max<right_max，则此时的结果可信，继续往右寻找,否则走2往左找
        2.否则从右往左找，此时的右边最大值是可信的，如果此时的right_max<left_max,则此时的结果可信，继续往左寻找，否则走1往右找
        :param height:
        :return:
        '''
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        res = 0
        while left <= right:
            if left_max < right_max:
                res += max(0, left_max - height[left])
                left_max = max(left_max, height[left])
                left += 1
            else:
                res += max(0, right_max - height[right])
                right_max = max(right_max, height[right])
                right -= 1

        return res


if __name__ == '__main__':
    # height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 2]
    # height = [4, 2, 0, 3, 2, 5]
    height = [0, 2, 0]
    height = [4, 2, 3]
    height = [5, 8, 9, 4, 9, 6, 1, 4]
    s = Solution()
    print(s.trap(height))
    print(s.trap_1(height))
